package io.github.handyang.algorithms.sort;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

@Slf4j
public class QuickSortAlgorithms implements SortAlgorithms {

    @Override
    public void sort(int[] arr) {
//        log.info("{}", Arrays.toString(arr));
        quick(arr, 0, arr.length - 1);
    }

    private void quick(int[] arr, int start, int end) {
//        log.info("start:{}, end:{}", start, end);
        if (start >= end) return;

        int i = start, j = end;
        int mid = ((end - start) >> 1) + start;

        int key = arr[mid];

        while (i < j) {
            while (i < j && less(key, arr[j])) j--;
            if (i < j) {
                arr[i++] = arr[j];
            }

            while (i < j && less(arr[i], key)) i++;
            if (i < j) {
                arr[j--] = arr[i];
            }
        }

        arr[i] = key;

        //非 mid
        if (i - 1 > start) quick(arr, start, i - 1);
        if (end > i + 1) quick(arr, i + 1, end);
    }
}
